/*
 * Copyright: Public Domain
 */
module nonstd.traits;

public import std.traits;
import std.typetuple;
import std.metastrings;


/**
Detect whether $(D func) is an abstract function.
 */
template isAbstractFunction(alias func,
        // [workaround] doesn't work inside template
        bool __r = __traits(isAbstractFunction, func))
{
    enum bool isAbstractFunction = __r;
}

unittest
{
    class C
    {
        void foo() {}
        abstract void bar();
        final void baz() {}
    }
    static assert(!isAbstractFunction!(C.foo));
    static assert( isAbstractFunction!(C.bar));
    static assert(!isAbstractFunction!(C.baz));
}


/**
Detect whether $(D func) is a final function.
 */
template isFinalFunction(alias func,
        // [workaround] doesn't work inside template
        bool __r = __traits(isFinalFunction, func))
{
    enum bool isFinalFunction = __r;
}

unittest
{
    class C
    {
        void foo() {}
        abstract void bar();
        final void baz() {}
    }
    static assert(!isFinalFunction!(C.foo));
    static assert(!isFinalFunction!(C.bar));
    static assert( isFinalFunction!(C.baz));
}


/*
[internal] [workaround] typeof(TypeTuple!()) doesn't work
 */
private template TypeOf(v...)
{
    static if (v.length)
        alias typeof(v) TypeOf;
    else
        alias TypeTuple!() TypeOf;
}

unittest
{
    static assert(is(TypeOf!(1, 2.0) == TypeTuple!(int, double)));
    static assert(TypeOf!().length == 0);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Function traits
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/**
These enumerated values represent storage classes in D.

Example:
--------------------
enum stoc = StorageClass.CONST | StorageClass.SHARED;
static assert(storageClassToString(stoc) == "const shared");
--------------------
 */
enum StorageClass : uint
{
    NONE,                /// No storage class
    CONST     = 1 <<  0, /// General storage classes
    IMMUTABLE = 1 <<  1, /// ditto
    SHARED    = 1 <<  2, /// ditto
    SCOPE     = 1 <<  3, /// ditto
    IN        = 1 <<  8, /// Parameter storage classes
    OUT       = 1 <<  9, /// ditto
    REF       = 1 << 10, /// ditto
    LAZY      = 1 << 11, /// ditto
}

/// Ditto
string storageClassToString(uint stoc)
{
    alias StorageClass SC;
    string str = "";

    for (uint mask = 1; mask <= stoc; mask <<= 1)
    {
        switch (stoc & mask)
        {
            case 0: break;
            case SC.CONST    : str ~=     "const "; break;
            case SC.IMMUTABLE: str ~= "immutable "; break;
            case SC.SHARED   : str ~=    "shared "; break;
            case SC.SCOPE    : str ~=     "scope "; break;
            case SC.IN       : str ~=        "in "; break;
            case SC.OUT      : str ~=       "out "; break;
            case SC.REF      : str ~=       "ref "; break;
            case SC.LAZY     : str ~=      "lazy "; break;
            default: assert(0);
        }
    }
    return str.length ? str[0 .. $ - 1] : str;
}


/**
These enumerated values represent function attributes in D.

Example:
--------------------
enum attrs = FuncAttr.PURE | FuncAttr.NOTHROW;
static assert(funcAttrToString(attrs) == "pure nothrow");
--------------------
 */
enum FuncAttr : uint
{
    NONE,             ///
    PURE    = 1 << 0, /// ditto
    NOTHROW = 1 << 1, /// ditto
    REF     = 1 << 2, /// ditto
}

/// Ditto
string funcAttrToString(uint attrs)
{
    alias FuncAttr FA;
    string str = "";

    for (uint mask = 1; mask <= attrs; mask <<= 1)
    {
        switch (attrs & mask)
        {
            case 0: break;
            case FA.PURE   : str ~=    "pure "; break;
            case FA.NOTHROW: str ~= "nothrow "; break;
            case FA.REF    : str ~=     "ref "; break;
            default: assert(0);
        }
    }
    return str.length ? str[0 .. $ - 1] : str;
}


/**
A $(D Linkage) value represents a linkage type in D, which are used in
$(D extern) attribute.

Example:
--------------------
static assert(linkageToString(Linkage.CPP) == "C++");
--------------------
 */
enum Linkage
{
    D,       ///
    C,       /// ditto
    WINDOWS, /// ditto
    PASCAL,  /// ditto
    CPP,     /// ditto
}

/// Ditto
string linkageToString(Linkage link)
{
    switch (link)
    {
        case Linkage.D      : return "D";
        case Linkage.C      : return "C";
        case Linkage.WINDOWS: return "Windows";
        case Linkage.PASCAL : return "Pascal";
        case Linkage.CPP    : return "C++";
        default: assert(0);
    }
}


/**
A $(D Variadic) value indicates whether a function is variadic or not.
There are two types of variadic functions in D:
--------------------
void foo(string s, int n, ...); // variadic function
void bar(string s, string[] args...); // typesafe variadic function
--------------------
and they are represented by $(D VARIADIC) and $(D TYPESAFE),
respectively.
 */
enum Variadic
{
    NO,       ///
    VARIADIC, /// ditto
    TYPESAFE, /// ditto
}


/**
Collection of various traits on the function or function type $(D F).
You can specify a $(D .name) property with $(D n) if $(D F) is a
function type.

Example:
--------------------
struct S
{
    extern (C)
    ref int foo(int a, lazy int b, uint[] c...) const nothrow;
}
alias FunctionTraits!(S.foo) F;

static assert(F.name == "foo");

static assert(F.storageClass == StorageClass.CONST);
static assert(F.attributes == FuncAttr.NOTHROW | FuncAttr.REF);
static assert(F.linkage == Linkage.C);

static assert(is(F.ReturnType == int));
static assert(is(F.ParameterTypeTuple ==
    TypeTuple!(int, int, uint[])));

static assert(F.parameterStorageClasses ==
    [ StorageClass.NONE, StorageClass.LAZY, StorageClass.NONE ]);
static assert(F.variadic == Variadic.TYPESAFE);
--------------------
 */
template FunctionTraits(F, string n = null)
    if (is(F == function))
{
    private enum deco = demangleFunc!(F);

    /**
     * The unqualified _name of the function.
     */
    enum string name = n;

    /**
     * A bit pattern representing the storage class of $(D F) itself. This is
     * a bitwise-OR of $(D StorageClass) enum values.
     */
    enum uint storageClass = deco.stoc;

    /**
     * A bit pattern representing the function _attributes. This is a
     * bitwise-OR of $(D FuncAttr) enum values.
     */
    enum uint attributes = deco.attr;

    /**
     * The calling convention.
     */
    enum Linkage linkage = deco.link;

    /**
     * The return type.
     */
    alias .ReturnType!(F) ReturnType;

    /**
     * The parameter type tuple.
     */
    alias .ParameterTypeTuple!(F) ParameterTypeTuple;

    /**
     * An array literal of the parameter storage classes.
     */
    //------------------
    // [workaround] "2: Error: cannot implicitly convert expression
    // ([2048u,0u]) of type StorageClass[] to StorageClass[]"
    //------------------
    alias extractPSCs!(F) parameterStorageClasses;
    //enum StorageClass[] parameterStorageClasses = extractPSCs!(F);

    /**
     * Indicates whether the function is _variadic or not.
     */
    enum Variadic variadic = deco.variadic;
}

/// Ditto
template FunctionTraits(alias F,
        __F = typeof(F) /* [workaround] typeof inside template may
                           return a wrong type */
        )
{
    mixin FunctionTraits!(__F, functionName!(F));

    /**
     * An alias to the function.
     */
    alias F func;
}

// [internal]
template FunctionTraits(string n,
        uint stoc, uint atts, Linkage link,
        R, alias psc, Variadic var, P...)
{
    enum string name = n;
    enum uint storageClass = stoc;
    enum uint attributes = atts;
    enum Linkage linkage = link;
    alias R ReturnType;
    alias P ParameterTypeTuple;
    enum StorageClass[] parameterStorageClasses = psc;
    enum Variadic variadic = var;
}

unittest
{
    struct S
    {
        extern (C)
        ref int foo(int a, lazy int b, uint[] c...) const nothrow;
    }
    alias FunctionTraits!(S.foo) ft;

    static assert(is(ft.Type == typeof(S.foo)));
    static assert(ft.name == "foo");

    static assert(ft.storageClass == StorageClass.CONST);
    static assert(ft.attributes == FuncAttr.NOTHROW | FuncAttr.REF);
    static assert(ft.linkage == Linkage.C);

    static assert(is(ft.ReturnType == int));
    static assert(is(ft.ParameterTypeTuple == TypeTuple!(int, int, uint[])));
    static assert(ft.parameterStorageClasses ==
        [ StorageClass.NONE, StorageClass.LAZY, StorageClass.NONE ]);

    static assert(ft.variadic == Variadic.TYPESAFE);
}


/*
[internal] Returns the unqualified name of the function $(D fun).
 */
template functionName(alias fun)
    if (is(typeof(fun) == function))
{
    enum string functionName =
        // [workaround] magic
        TypeTuple!(fun).stringof[6 .. $ - 1];
}

unittest
{
    interface I
    {
        int foobar(int) const nothrow;
    }
    static assert(functionName!(I.foobar) == "foobar");
}


/*
[internal] [CTFE] Parses F.mangleof and extracts information as a
$(D FuncDeco) struct. The storage class, function attributes, linkage,
and variadicity are extracted. Parameter storage classes are not dealt
with; they will be extracted by another template $(D extractPSCs).

TypeFunction
  ::=  CallConvention FuncAttr* Argument* ArgClose Type
 */
private struct FuncDeco
{
    int stoc;
    int attr;
    Linkage link;
    Variadic variadic;
}

private template demangleFunc(F) // [workaround] bug 2414
{
    enum demangleFunc = demangleFuncImpl!(F)();
}

private FuncDeco demangleFuncImpl(F)()
{
    string deco = (F*).mangleof; // [workaround] compile error

    int stoc;
    int attr;
    Linkage link;
    Variadic var;

    // Pointer to...
    while (deco[0] == 'P')
        deco = deco[1 .. $];

    // Storage class
    while (deco.length)
    {
        StorageClass s;

        switch (deco[0])
        {
            case 'O': s = StorageClass.SHARED;    break;
            case 'x': s = StorageClass.CONST;     break;
            case 'y': s = StorageClass.IMMUTABLE; break;
            default: break;
        }
        if (s == StorageClass.init)
            break;

        stoc |= s;
        deco  = deco[1 .. $];
    }

    // Calling convention
    switch (deco[0])
    {
        case 'F': link = Linkage.D;       break;
        case 'U': link = Linkage.C;       break;
        case 'W': link = Linkage.WINDOWS; break;
        case 'V': link = Linkage.PASCAL;  break;
        case 'R': link = Linkage.CPP;     break;
        default: assert(0);
    }
    deco = deco[1 .. $];

    // Function attributes
    while (deco.length >= 2)
    {
        FuncAttr a;

        switch (deco[0 .. 2])
        {
            case "Na": a = FuncAttr.PURE;    break;
            case "Nb": a = FuncAttr.NOTHROW; break;
            case "Nc": a = FuncAttr.REF;     break;
            default: break;
        }
        if (a == FuncAttr.init)
            break;

        attr |= a;
        deco  = deco[2 .. $];
    }

    // [workaround] ReturnType!(F).mangleof may be wrong
    enum rdeco = (ReturnType!(F)*).mangleof[1 .. $];

    // We won't parse Arguments. Skip it.
    deco = deco[$ - (rdeco.length + 1) .. $];

    // Function variadicity
    switch (deco[0])
    {
        case 'X': var = Variadic.TYPESAFE; break;
        case 'Y': var = Variadic.VARIADIC; break;
        case 'Z': var = Variadic.NO;       break;
        default: assert(0);
    }
    deco = deco[1 .. $];

    // We don't need return type. The end.
    return FuncDeco(stoc, attr, link, var);
}

unittest
{
    struct S
    {
        extern (C) ref int foo(int, ...) const shared nothrow;
    }
    enum deco = demangleFunc!(typeof(S.foo));
    static assert(deco.stoc == StorageClass.CONST | StorageClass.SHARED);
    static assert(deco.attr == FuncAttr.NOTHROW | FuncAttr.REF);
    static assert(deco.link == Linkage.C);
    static assert(deco.variadic == Variadic.VARIADIC);
}


/*
[internal] Extracts the parameter storage classes of the function F and
returns them in an array literal.
 */
private template extractPSCs(F)
    if (is(F == function))
{
    enum extractPSCs = cast(StorageClass[]) extractPSCsImpl!(F).result;
}

private template extractPSCsImpl(F, size_t i = 0)
{
    static if (i < ParameterTypeTuple!(F).length)
        enum uint[] result =
                // [workaround] Error: cannot implicitly convert
                // expression ([0u]) of type uint[1u] to StorageClass[]
                __asUint!(
                    // [workaround] indexing drops parameter storage class
                    // but direct slicing doesn't
                    parsePSC(ParameterTypeTuple!(F)[i .. i + 1]
                        .stringof[1 .. $ - 1])) ~
                extractPSCsImpl!(F, i + 1).result;
    else
        enum uint[] result = [];
}
private template __asUint(StorageClass sc) // [workaround]
{
    enum uint __asUint = cast(uint) sc;
}

// [CTFE] Parse a parameter .stringof and returns the stoc.
private StorageClass parsePSC(string ptype)
{
    static string before(string s, char c)
    {
        foreach (i, e; s)
            if (e == c)
                return s[0 .. i];
        return s;
    }
    switch (before(ptype, ' '))
    {
        case "scope": return StorageClass.SCOPE;
        case    "in": return StorageClass.IN;
        case   "out": return StorageClass.OUT;
        case   "ref": return StorageClass.REF;
        case  "lazy": return StorageClass.LAZY;
        default: break;
    }
    return StorageClass.init;
}

unittest
{
    alias StorageClass SC;
    void foo(scope int, in int, out int, ref int, lazy int);

    enum pscs = extractPSCs!(typeof(foo));
    static assert(pscs == [ SC.SCOPE, SC.IN, SC.OUT, SC.REF, SC.LAZY ]);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Overload set
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/**
Groups function overloads $(D fs) in a template instance.
 */
template OverloadSet(string n, fs...)
{
    /**
     * A tuple consisting of (possibly types of) all _overloads in the
     * overload set.
     */
    alias fs overloads;

    /**
     * The overloaded _name. This property is available if the argument
     * $(D n) is given.
     */
    enum string name = n;
}

/// Ditto
template OverloadSet(fs...)
{
    alias fs overloads;
}

// [internal]
private template GiveName(string name, osets...)
{
    alias GiveNameImpl!(name, osets).sets GiveName;
}
private template GiveNameImpl(string name, osets...)
{
    static if (osets.length)
    {
        // [workaround] "tuple is not a valid template parameter"
        alias osets[0] o;

        alias TypeTuple!(
            OverloadSet!(name, o.overloads),
            GiveNameImpl!(name, osets[1 .. $]).sets) sets;
    }
    else
    {
        alias TypeTuple!() sets;
    }
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Method names
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/*
[workaround] bug 2997: allMembers does not return interface members.
 */
private template allMembers(C)
{
    enum allMembers = allMembersImpl!(C).all;
}

// [internal]
private template allMembersImpl(C)
{
    private static T[] nodup(T)(T[] arr)
    {
        T[] r;

        for (size_t i = 0; i < arr.length; ++i)
        {
            auto e = arr[i];

            for (size_t j = i + 1; j < arr.length; ++j)
            {
                if (arr[j] == e)
                    arr = arr[0 .. j] ~ arr[j + 1 .. $];
            }
            r ~= e;
        }
        return r;
    }

    template dig(I...)
    {
        static if (I.length)
            enum string[] dig =
                (cast(string[]) __traits(allMembers, I[0])) ~
                dig!(I[1 .. $]);
        else
            enum string[] dig = [];
    }

    enum all = nodup(dig!(C, InterfacesTuple!(C)));
}


/**
Returns an array literal of strings, each of which is a non-static
member function name defined in $(D C) and its ancestors. The result
does not contain duplicate names.

Example:
--------------------
import std.stdio;
interface I { void foo(); }
interface J { void bar(); }
abstract class C : I, J
{
    void bar(int);
    static void baz();
}
void main()
{
    writeln(methodNames!(C));
}
--------------------
which prints
--------------------
bar toString toHash opCmp opEquals foo
--------------------
 */
template methodNames(C)
{
    // The raw result of allMembers contains member variables.
    enum methodNames = selectMethodNames!(C, allMembers!(C));
}

// [internal]
private template selectMethodNames(C, alias names)
{
    static if (names.length)
    {
        // to allow only non-static member function names in the result
        static if (MethodOverloadsTuple!(C, names[0]).length)
            enum selectMethodNames = names[0] ~
                selectMethodNames!(C, names[1 .. $]);
        else
            enum selectMethodNames =
                selectMethodNames!(C, names[1 .. $]);
    }
    else
    {
        enum selectMethodNames = names; // empty
    }
}

unittest
{
    // Are a and b are equal (regardless of order)?
    static bool consistsOf(T)(T[] a, T[] b)
    {
        if (a.length != b.length)
            return false;
        static bool impl(T[] a, T[] b, size_t n)
        {
            if (a.length == 0)
                return true;
            if (n == a.length)
                return false;
            if (a[0] == b[0])
                return consistsOf(a[1 .. $], b[1 .. $]);
            return impl(a[1 .. $] ~ a[0], b, n + 1);
        }
        return impl(a, b, 0);
    }
    struct WorkaroundForBug2986
    {
        interface I
        {
            void foo();
            void foo(int);
            void bar();
        }
        static assert(consistsOf(methodNames!(I), [ "foo", "bar" ]));

        class B        { abstract void foo(); int x; }
        class C : B, I { abstract void bar(); static void baz() {} }
        enum o = methodNames!(Object);
        enum b = methodNames!(B);
        enum c = methodNames!(C);
        static assert(consistsOf(b, o ~ [ "foo" ]));
        static assert(consistsOf(c, o ~ [ "foo", "bar" ]));
    }
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Method overloads
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/**
Returns a static tuple consisting of all [abstract/final] member
function overloads of the name $(D m) defined in $(D C) and its
ancestors. The tuple will not contain any duplicates. Covariant
overloads are not removed.

Example:
--------------------
interface I { I foo(); }
interface J { J foo(); I foo(); }
class C : I, J
{
    final C foo() { return null; }
}
pragma(msg, typeof(        MethodOverloadsTuple!(C, "foo")).stringof);
pragma(msg, typeof(AbstractMethodOverloadsTuple!(C, "foo")).stringof);
pragma(msg, typeof(   FinalMethodOverloadsTuple!(C, "foo")).stringof);
--------------------
which prints
--------------------
(C(), I(), J())
(I(), J())
(C())
--------------------
 */
template MethodOverloadsTuple(C, string m)
{
    alias MethodOverloadsTupleImpl!(C, m).all
        MethodOverloadsTuple;
}

// [internal]
private template MethodOverloadsTupleImpl(C, string m)
{
    /*
     * The getVirtualFunctions trait returns a weird tuple, not
     * usual static tuple. This template just does a convertion.
     */
    template scopeOverloads()
    {
        enum max = __traits(getVirtualFunctions, C, m).length;

        template next(size_t i)
        {
            static if (i < max)
                alias TypeTuple!(
                        __traits(getVirtualFunctions, C, m)[i],
                        next!(i + 1)
                    ) next;
            else
                alias TypeTuple!() next;
        }
        alias next!(0) all;
    }

    /*
     * This template gathers overloads in ancestor classes and
     * interfaces. There would be duplicates in the result.
     *
     * Note: getVirtualFunctions actually returns an overload set, not
     * all overloads. I.e., hidden functions are excluded. That's why
     * this template is needed.
     */
    template ancestorsOverloads()
    {
        template dig(C...)
        {
            static if (C.length)
                alias TypeTuple!(
                        MethodOverloadsTuple!(C[0], m),
                        dig!(C[1 .. $])
                    ) dig;
            else
                alias TypeTuple!() dig;
        }

        static if (is(C S == super))
            alias dig!(S) all;
        else
            alias TypeTuple!() all;
    }

    /*
     * [workaround] std.typetuple.NoDuplicates is not functional
     */
    template remove(alias m, ms...)
    {
        static if (ms.length)
        {
            static if (is(typeof(m) == typeof(ms[0])))
                alias remove!(m, ms[1 .. $]) remove;
            else
                alias TypeTuple!(ms[0], remove!(m, ms[1 .. $])) remove;
        }
        else
        {
            alias TypeTuple!() remove;
        }
    }
    template removeDuplicates(ms...)
    {
        static if (ms.length)
            alias TypeTuple!(ms[0],
                    removeDuplicates!(remove!(ms[0], ms[1 .. $]))
                ) removeDuplicates;
        else
            alias TypeTuple!() removeDuplicates;
    }

    /*
     * Doit.
     */
    static if (__traits(hasMember, C, m))
        alias TypeTuple!(
                scopeOverloads!().all,
            ancestorsOverloads!().all) raw;
    else
        alias ancestorsOverloads!().all raw;

    alias removeDuplicates!(raw) all;
}

unittest
{
    struct WorkaroundForBug2986_Test1
    {
        interface I     { void foo(); }
        interface J : I { void foo(int); }
        class A : J { abstract void foo(int, int); }
        class B : A { abstract void foo(int, int, int); }
        class C : B
        {
            abstract void foo(int, int, int, int);
            abstract void bar();
        }
        static assert(PackedTuple!(MethodOverloadsTuple!(C, "foo"))
            .consistsOf!(I.foo, J.foo, A.foo, B.foo, C.foo));
    }
    // test for duplicate methods
    struct WorkaroundForBug2986_Test2
    {
        interface I { void foo(int); }
        interface J { void foo(int); }
        class C : I, J
        {
            void foo(int) {}
        }
        static assert(PackedTuple!(MethodOverloadsTuple!(C, "foo"))
            .consistsOf!(C.foo));
    }
}

/**
Ditto
 */
template AbstractMethodOverloadsTuple(C, string m)
{
    alias staticFilter!(isAbstractFunction, MethodOverloadsTuple!(C, m))
        AbstractMethodOverloadsTuple;
}

/**
Ditto
 */
template FinalMethodOverloadsTuple(C, string m)
{
    alias staticFilter!(isFinalFunction, MethodOverloadsTuple!(C, m))
        FinalMethodOverloadsTuple;
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// All methods
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/**
Returns a static tuple consisting of all [abstract/final] member
functions defined in $(D C) and its ancestors. The tuple will not
contain any duplicates. Covariant overloads are not removed.

Example:
--------------------
class C
{
    void foo();
    abstract void bar(int);
    final ref int baz(int, short) { return v; }
    int v;
}
pragma(msg, MethodsTuple!(C).stringof);
--------------------
which prints
--------------------
tuple(foo,bar,toString,toHash,opCmp,opEquals)
--------------------
 */
template MethodsTuple(C)
{
    alias MethodsTupleImpl!(C, methodNames!(C)) MethodsTuple;
}

// [internal]
private template MethodsTupleImpl(C, alias mnames)
{
    static if (mnames.length)
        alias TypeTuple!(
                MethodOverloadsTuple!(C, mnames[0]),
                MethodsTupleImpl!(C, mnames[1 .. $])
            ) MethodsTupleImpl;
    else
        alias TypeTuple!() MethodsTupleImpl;
}

/**
Ditto
 */
template AbstractMethodsTuple(C)
{
    alias staticFilter!(isAbstractFunction, MethodsTuple!(C))
        AbstractMethodsTuple;
}

/**
Ditto
 */
template FinalMethodsTuple(C)
{
    alias staticFilter!(isFinalFunction, MethodsTuple!(C))
        FinalMethodsTuple;
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Covariant functions
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/**
Returns true if a function type $(D Fa) is covariant to $(D Fb); i.e.
their parameter types are the same, return types are covariant, calling
conventions match, and both or none of two are ref functions.

Example:
--------------------
interface X     {}
interface Y : X {}

X foo(lazy int a);
Y bar(lazy int a);
Y baz(     int a);
static assert( isCovariant!(typeof(foo), typeof(bar)));
static assert(!isCovariant!(typeof(bar), typeof(baz)));
--------------------
 */
template isCovariant(Fa, Fb)
{
    enum isCovariant = is(Fa == Fb) ||
        __traits(compiles, CovariantFunctionType!(Fa, Fb));
}

unittest
{
    class A
    {
    abstract:
        ref int foo(lazy int, short[] ...) const;
        ref int bar(lazy int, short[] ...) nothrow;
            int baz(lazy int, short[] ...) pure;
    }
    static assert( isCovariant!(typeof(A.foo), typeof(A.bar)));
    static assert(!isCovariant!(typeof(A.bar), typeof(A.baz)));
    static assert(!isCovariant!(typeof(A.baz), typeof(A.foo)));
}


/**
Returns the type of a function that can 'override' function types
$(D Fs), or just returns $(D Fs[0]) if $(D Fs.length == 1).

All functions in $(D Fs) must be covariant overloads (see the
description of $(D isCovariant).); otherwise, throws a compile-time
assertion error.

Example:
--------------------
interface X     {}
interface Y : X {}

interface I { X foo() nothrow; }
interface J { Y foo() const; }
alias CovariantFunctionType!(typeof(I.foo), typeof(J.foo)) Cov;

interface K : I, J
{
    override Y foo() const nothrow; // overrides I.foo and J.foo
}
static assert(is(Cov == typeof(K.foo)));
--------------------
 */
template CovariantFunctionType(Fs...)
    if (Fs.length >= 1)
{
    alias staticReduce!(CovariantFunctionTypePrim, Fs)
        CovariantFunctionType;
}

unittest
{
    struct WorkaroundForBug2986
    {
        interface X     {}
        interface Y : X {}
        interface Z : Y {}

        interface I { X foo(lazy int, ...) immutable pure; }
        interface J { Y foo(lazy int, ...) nothrow; }
        interface K { Z foo(lazy int, ...) const; }
        interface L : I, J, K
        {
            override Z foo(lazy int, ...) const pure nothrow;
        }
        alias TypeOf!(I.foo, J.foo, K.foo) FF;
        alias CovariantFunctionType!(FF) Fcov;
        static assert(is(Fcov == typeof(L.foo)));
    }
}

/*
[internal] Returns the function type covariant to Fa and Fb.
 */
private template CovariantFunctionTypePrim(Fa, Fb)
{
    alias CovariantFunctionTypePrimImpl!(Fa, Fb).Type
        CovariantFunctionTypePrim;
}

// [internal] Returns the common function storage class of a and b.
private uint commonStorageClass(uint a, uint b)
{
    uint c = a | b;

    if (((a | b) & StorageClass.CONST) ||   // either a or b is const
        ((a ^ b) & StorageClass.IMMUTABLE)) // a xor b is immutable
    {
        // Remove immutable and make it const.
        c = (c & ~StorageClass.IMMUTABLE) | StorageClass.CONST;
    }
    return c;
}

// [internal]
private template CovariantFunctionTypePrimImpl(Fa, Fb)
{
private:
    // [workaround] Fa.stringof does not work
    enum Fa_stringof = TypeTuple!(Fa).stringof[1 .. $ - 1];
    enum Fb_stringof = TypeTuple!(Fb).stringof[1 .. $ - 1];

    enum notcov = "No covariant override can be derived from function "
        " types < " ~ Fa_stringof ~ " > and < " ~ Fb_stringof ~ " >";

    alias FunctionTraits!(Fa) FTa;
    alias FunctionTraits!(Fb) FTb;

    /*
     * Derive the function attributes and storage class.
     */
    enum Sa = FTa.storageClass, Aa = FTa.attributes;
    enum Sb = FTb.storageClass, Ab = FTb.attributes;
    static assert(((Aa ^ Ab) & FuncAttr.REF) == 0,
            notcov ~ " (ref and nonref functions)");
    enum Scov = commonStorageClass(Sa, Sb);
    enum Acov = Aa | Ab;

    /*
     * Derive the calling convention.
     */
    enum La = FTa.linkage;
    enum Lb = FTb.linkage;
    static assert(La == Lb, notcov ~ " (different linkage)");
    enum Lcov = La;

    /*
     * Derive the covariant return type.
     */
    alias FTa.ReturnType Ra;
    alias FTb.ReturnType Rb;

    static if (is(Ra : Rb))
        alias Ra Rcov;
    else static if (is(Rb : Ra))
        alias Rb Rcov;
    else
        static assert(0, notcov ~ " (return types not covariant)");

    /*
     * Parameter types.
     */
    alias FTa.ParameterTypeTuple Pa;
    alias FTb.ParameterTypeTuple Pb;
    static assert(is(TypeTuple!(Pa) == TypeTuple!(Pb)),
            notcov ~ " (parameter types mismatch)");
    alias Pa Pcov;

    alias FTa.parameterStorageClasses PSCa;
    alias FTb.parameterStorageClasses PSCb;
    static assert(PSCa == PSCb,
            notcov ~ " (parameter storage classes mismatch)");
    alias PSCa PSCcov;

    enum Va = FTa.variadic;
    enum Vb = FTb.variadic;
    static assert(Va == Vb, notcov ~ " (variadic mismatch)");
    enum Vcov = Va;

    /*
     * Actually generate a function to obtain the covariant type.
     */
    // Generates a function signature.
    string signature(string name)
    {
        enum link = "extern (" ~ linkageToString(Lcov) ~ ")";
        enum stoc = storageClassToString(Scov);
        enum atts = funcAttrToString(Acov);
        enum mod  = link ~ " " ~ stoc ~ " " ~ atts;

        // Generate parameter declarations
        string ptypes = "";

        foreach (i, P; Pcov)
        {
            static if (i >= 1)
                ptypes ~= ", ";
            ptypes ~= storageClassToString(PSCcov[i]);
            ptypes ~= " Pcov[" ~ ToString!(i) ~ "]";
        }

        // classic ( a, b, c, ... ) or ( ... )
        static if (Vcov == Variadic.VARIADIC)
            ptypes ~= Pcov.length ? ", ..." : "...";

        // typesafe ( a, b, c ... )
        static if (Vcov == Variadic.TYPESAFE)
            ptypes ~=   "...";

        return mod ~ " Rcov " ~ name ~ "(" ~ ptypes ~ ")";
    }

    interface Dummy
    {
        mixin (signature("dummy") ~ ";");
    }
    public alias typeof(Dummy.dummy) Type;
}

unittest
{
    struct S
    {
        ref int foo(in int n, ...) nothrow;
        ref int bar(in int n, ...) const;
        ref int cov(in int n, ...) const nothrow;
    }
    alias CovariantFunctionTypePrim!(typeof(S.foo), typeof(S.bar)) Cov;
    static assert(is(Cov == typeof(S.cov)));
}


/**
Classifies the functions $(D fs) into covariant overload sets.

Example:
--------------------
interface X     {}
interface Y : X {}

interface I { X   foo(); }
interface J { Y   foo(); }
interface K { int foo(); }
interface L { X   bar(); }

alias CovariantOverloadSets!(I.foo, J.foo, K.foo, L.bar) Cov;
alias Cov[0] Cov_foo1; // (I.foo, J.foo)
alias Cov[1] Cov_foo2; // (K.foo)
alias Cov[2] Cov_bar;  // (L.bar)

static assert(PackedTuple!(Cov_foo1.overloads).equals!(I.foo, J.foo));
static assert(PackedTuple!(Cov_foo2.overloads).equals!(K.foo));
static assert(PackedTuple!(Cov_bar .overloads).equals!(L.bar));
--------------------
Note that $(D K.foo) is in a separate overload set. This is because
$(D K.foo) returns $(D int), which is not covariant to neither $(D X)
nor $(D Y). $(D L.bar) is in another overload set since its name is
different from the others.
 */
template CovariantOverloadSets(fs...)
{
    alias CollectCovariants!(fs).result CovariantOverloadSets;
}

// [internal]
private template CollectCovariants()
{
    alias TypeTuple!() result;
}
private template CollectCovariants(alias fhead, ftail...)
{
    alias typeof(fhead) Fhead;
    enum ovname = functionName!(fhead);

    static if (ftail.length)
    {
        template isCovariantOverload(alias f, _F = typeof(f))
        {
            enum isCovariantOverload =
                functionName!(f) == ovname &&
                isCovariant!(Fhead, _F);
        }
        alias staticPartition!(isCovariantOverload, ftail) p;

        alias TypeTuple!(
                OverloadSet!(ovname, fhead, p.take),
                CollectCovariants!(p.drop).result
            ) result;
    }
    else
    {
        alias TypeTuple!(OverloadSet!(ovname, fhead)) result;
    }
}

unittest
{
    struct WorkaroundForBug2986
    {
        interface X     {}
        interface Y : X {}

        interface I { X   foo(); }
        interface J { Y   foo(); }
        interface K { int foo(); }
        interface L { X   bar(); }

        alias CovariantOverloadSets!(I.foo, J.foo, K.foo, L.bar) Cov;
        alias Cov[0] Cov_fooA; // (I.foo, J.foo)
        alias Cov[1] Cov_fooB; // (K.foo)
        alias Cov[2] Cov_bar;  // (L.bar)
        static assert(PackedTuple!(Cov_fooA.overloads).equals!(I.foo, J.foo));
        static assert(PackedTuple!(Cov_fooB.overloads).equals!(K.foo));
        static assert(PackedTuple!(Cov_bar .overloads).equals!(L.bar));
    }
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/**
Returns a tuple of $(D FunctionTraits), each of which is the traits on
a function that can override an overload set in $(D ovs).

Example:
--------------------
interface X     {}
interface Y : X {}

interface I { X foo() const; }
interface J { Y foo() nothrow; }
class C : I, J
{
    abstract void bar(int);
}

alias OverrideTraitsTuple!(
    CovariantOverloadSets!(AbstractMethodsTuple!(C))) OTT;
static assert(OTT.length == 2);
pragma(msg, OTT[0].name, " = ", OTT[0].Type.stringof);
pragma(msg, OTT[1].name, " = ", OTT[1].Type.stringof);
--------------------
which prints
--------------------
bar = void(int)
foo = const nothrow Y()
--------------------
 */
template OverrideTraitsTuple(ovs...)
{
    alias staticMap!(OverrideTraits_Merge, ovs) OverrideTraitsTuple;
}

// [internal] Merge overloads in an overload set os.
private template OverrideTraits_Merge(alias os)
{
    alias FunctionTraits!(
            CovariantFunctionType!(typeof(os.overloads)), os.name)
        OverrideTraits_Merge;
}

unittest
{
    struct WorkaroundForBug2986
    {
        interface X     {}
        interface Y : X {}

        interface I { X foo() const; }
        interface J { Y foo() nothrow; }
        class C : I, J
        {
            abstract void bar(int);
        }
        class W
        {
            Y foo() const nothrow { return null; }
            void bar(int) {}
        }

        alias OverrideTraitsTuple!(
            CovariantOverloadSets!(AbstractMethodsTuple!(C))) OTT;
        static assert(OTT.length == 2);
        alias OTT[0] OTT_bar;
        alias OTT[1] OTT_foo;

        static assert(OTT_bar.name == "bar");
        static assert(OTT_foo.name == "foo");
        static assert(is(OTT_bar.Type == typeof(W.bar)));
        static assert(is(OTT_foo.Type == typeof(W.foo)));
    }
}

